function radixSort(arr) {
  //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
  //说明
  //1，二维数组包含10个一维数组，
  //2.为了防止在放入数的时候，数据溢出，则每个一维数组（桶）
  //大小定为arr.length
  //3.很明确，基数排序是使用空间换时间的经典算法
  let bucket = new Array(10);
  for (let i = 0; i < bucket.length; i++) {
    bucket[i] = new Array(arr.length);
  }
  //为了记录每个桶中，实际存了多少个数据，我们定义一个
  //一维数组来记录每个桶的每次放入的数据个数
  //可以这里理解
  //比如：bucketElementCounts[0],记录的就是bucket[0]桶的放入数据个数
  let buckeElementCounts = new Array(10).fill(0);

  //1.得到数组中最大的位数
  let max = arr[0];
  let min = 0
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i]
    }
    if (arr[i] < min) {
      min = arr[i];//找到负数最小值			
    }
  }
  if (min < 0) {
    for (let mi = 0; mi < arr.length; mi++) {
      arr[mi] -= min;
      max -= min;
    }
  }
  //得到最大是几位数
  let maxLength = (max + '').length;
  for (let i = 0, n = 1; i < maxLength; i++, n = n * 10) {
    //每一轮，对每个元素的各个位数进行排序处理,
    //第一次是个位，第二次是十位，第三次是百位
    for (let j = 0; j < arr.length; j++) {
      //取出每个元素的各位的值
      let digitOfElement = Math.floor(arr[j] / n) % 10;
      bucket[digitOfElement][buckeElementCounts[digitOfElement]]
        = arr[j];
      buckeElementCounts[digitOfElement]++;
    }
    //按照这个桶的顺序（以为数组的下标依次取出数据，放入原来数组）
    let index = 0;
    //遍历每一桶，并将桶中的数据，放入原数组
    for (let k = 0; k < buckeElementCounts.length; k++) {
      //如果桶中有数据，我们才放入原数组
      if (buckeElementCounts[k] !== 0) {
        //循环该桶即第k个桶，即第k个一维数组，放入
        for (let l = 0; l < buckeElementCounts[k]; l++) {
          //取出元素放入arr
          arr[index] = bucket[k][l];
          //arr下标后移
          index++;
        }
        //每轮处理后，下标要清0
        buckeElementCounts[k] = 0;
      }
    }
  }
  if (min < 0) {
    for (let mi = 0; mi < arr.length; mi++) {
      arr[mi] += min;
    }
  }
  return arr
}


const arr = [2, 1, 10, 8, 5, 4, 7, 3, 9, 6, 0, -1, -2, 2 * 1, 3 * -1, 1 - 5]
console.log(radixSort(arr));

// ** 基数排序 属于“桶子法” 基数也就是“进制”的意思     
// ** 将整数按位数切割成不同的数字，然后按每个位数分别比较 也是一种桶排序。桶排序是按值区间划分桶，基数排序是按数位来划分。
// 很明确，基数排序是使用空间换时间的经典算法       
// 1.将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。
// 然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
// 2.将所有待排序整数（注意，必须是非负整数）统一为位数相同的整数，位数较少的前面补零。一般用10进制，也可以用16进制甚至2进制。

// ** 举例:  10001    00023   00221   03229   补全后 个十百千往上 比对

// ** 注意点:
// 网上很多版本的基数排序存在问题对于包含负数和0的数据以及小数无法进行排序
// ! 我们这里这版做了些优化，可以排负数，但浮点数不行    
// ! 根据整数的数字规律 只有0-9 个十百千都是如此  小数的话理论上也可以继续下去，但是要特殊化去兼容